class Node {
  constructor(key, value) {
    this.key = key;
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}


/**
 * @param {number} capacity
 */
var LRUCache = function(capacity) {
  this.capacity = capacity;
  this.map = new Map();
  this.size = 0;
  this.dumpyHead = new Node();
  this.dumpyTail = new Node();
  this.dumpyHead.next = this.dumpyTail;
  this.dumpyTail.prev = this.dumpyHead;
};


/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
  let node = this.map.get(key);
  if (!node) {
    return -1;
  }
  // move node to the front
  this.moveToFront(node);
  return node.value;
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
  let node = this.map.get(key);
  if (!node) {
    // 容量满了
    if (this.size === this.capacity) {
      this.removeLRU();
    }
    let newNode =new Node(key, value);
    this.add(newNode);
    this.map.set(key, newNode);
    this.size++;
  } else {
    // 更新节点的值
    node.value = value;
    this.moveToFront(node);
  }
};

// 封装add和remove方法
LRUCache.prototype.moveToFront = function(node) {
  this.remove(node);
  this.add(node);
}

// 封装删除最长时间未使用的节点
LRUCache.prototype.removeLRU = function() {
  let temp = this.removeTail();
  this.deleteMapNode(temp);
  this.size--;
}

// 将节点加入到链表头
LRUCache.prototype.add = function(node) {
  node.prev = this.dumpyHead;
  node.next = this.dumpyHead.next;
  this.dumpyHead.next.prev = node;
  this.dumpyHead.next = node;
}

// 将节点从链表中移除
LRUCache.prototype.remove = function(node) {
  let temp1 = node.prev;
  let temp2 = node.next;
  temp1.next = temp2;
  temp2.prev = temp1;
}

// 移除链表的最后一个节点
LRUCache.prototype.removeTail = function() {
  let temp = this.dumpyTail.prev;
  this.remove(temp);
  return temp;
}

// 从map中删除对应的节点
LRUCache.prototype.deleteMapNode = function(node) {
  this.map.delete(node.key);
}